/*
 * Treap.h
 *
 *  Created on: Sep 15, 2012
 *      Author: jeffrey
 */

#ifndef TREAP_H_
#define TREAP_H_
#include<iostream>
#include<cstdlib>
#include<list>
#include<string>
#include<sstream>
namespace tree {
using namespace std;
class Treap {
	class Node {
	public:
		Node* left;
		Node* right;
		Node* parent;
		int v;
		int treapV;
		Node(int v = 0) {
			this->v = v;
			left = NULL;
			right = NULL;
			parent = NULL;
			treapV = rand();

		}
		string toString() {
			string result = "";
			list<Node*> queue;
			queue.push_back(this);
			queue.push_back(NULL);
			while (!queue.empty()) {
				Node* tmp = queue.front();
				queue.pop_front();
				if (tmp == NULL) {
					result.append("\n");
					if (!queue.empty())
						queue.push_back(NULL);
				} else {
					result.append(" ");
					ostringstream os;
					os << tmp->v;
					result.append(os.str());
					if (tmp->left != NULL)
						queue.push_back(tmp->left);
					if (tmp->right != NULL)
						queue.push_back(tmp->right);
				}
			}

			return result;
		}
	};
public:
	Treap();
	virtual ~Treap();
	string toString() {
		return root == NULL ? "" : root->toString();
	}
	void insert(int value) {
		if (root == NULL)
			root = new Node(value);
		else {
			Node* node = new Node(value);
			Node* n = root;
			while (n != NULL) {
				if (n->v < value) {
					if (n->right == NULL) {
						n->right = node;
						node->parent = n;
						break;
					} else
						n = n->right;
				} else {
					if (n->left == NULL) {
						n->left = node;
						node->parent = n;
						break;
					} else
						n = n->left;
				}
			}
			while (n->parent != NULL && n->parent->treapV >= n->treapV) {
				if (n == n->parent->left)
					right_rotate(*(n->parent));
				else
					left_rotate(*(n->parent));
			}
		}
	}
	Node* find(int value) {
		Node* n = root;
		while (n != NULL) {
			if (n->v == value)
				return n;
			else if (n->v < value)
				n = n->right;
			else
				n = n->left;
		}
		return NULL;
	}
private:
	Node* root;
	void left_rotate(Node& node) {
		if (node.right != NULL) {
			Node* right = node.right;
			right->parent = node.parent;
			if (right->parent != NULL) {
				if (&node == node.parent->left)
					right->parent->left = right;
				else
					right->parent->right = right;
			} else
				root = right;
			Node* left = right->left;
			right->left = &node;
			node.parent = right;
			node.right = left;
			if (left != NULL)
				left->parent = &node;
		}
	}
	void right_rotate(Node& node) {
		if (node.left != NULL) {
			Node* left = node.left;
			left->parent = node.parent;
			if (left->parent != NULL) {
				if (&node == node.parent->left)
					left->parent->left = left;
				else
					left->parent->right = left;
			} else
				root = left;
			Node* right = left->right;
			left->right = &node;
			node.parent = left;
			node.left = right;
			if (right != NULL)
				right->parent = &node;
		}
	}
};

} /* namespace structure */
#endif /* TREAP_H_ */
